package com.hw3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class ParseExpression {

    public static List<String> stringTokenizer(String input){
        int len=input.length();
        List<String> inp=new ArrayList<String>();
        for(int i=0,j=0;i<len;i++){
            if(i+1!=len && ((input.charAt(i)-'0'<10 && input.charAt(i)-'0'>=0) || input.charAt(i)=='.') && 
                    ((input.charAt(i+1)-'0'<10 && input.charAt(i+1)-'0'>=0) || input.charAt(i+1)=='.')){
                continue;
            }
            else{
                inp.add(input.substring(j,i+1));
                j=i+1;
            }
        }
        return inp;
    }
    
    public static void testStringTokenizer(){
        String s="1+(20.7*3)-7/(7-5)";
        List<String> inp=stringTokenizer(s);
        for (String string : inp) {
            System.out.print(string+" ");
        }
    }
    
    public static Map<String,Integer> precedenceOrder(){
        Map<String,Integer> pre=new HashMap<String,Integer>();
        String[] operator={"^","/","*","+","-"};
        for(int i=0;i<operator.length;i++){
            pre.put(operator[i], operator.length-i);
        }
        return pre;
    }
    
    public static boolean precedenceOrder(Map<String,Integer> pre,String s1,String s2){
        return pre.get(s1)>pre.get(s2);
    }
    private static Double getOperationValue(Double first, Double last,String operatr) {
        switch (operatr){
            case "+":return first+last;
            case "/":return first/last;
            case "*":return first*last;
            case "-":return first-last;
            case "^":return Math.pow(first, last);
        }
        return null;
    }
    
    
    public static void shuntingYardRPN(String input){
        List<String> inp=stringTokenizer(input);
        Stack<String> operand=new Stack<String>();
        List<String> rpn=new ArrayList<String>(); 
        Map<String,Integer> prec=precedenceOrder();
        for(String ch:inp){
        	if("(".equals(ch))
        		operand.add(ch);
        	else if(")".equals(ch)){
        		while(!"(".equals(operand.peek())){
        			rpn.add(operand.pop());
        		}
        		operand.pop();
        	}
        	else if(!prec.containsKey(ch))
        		rpn.add(ch);
        	else if(prec.containsKey(ch)){
        		while(!operand.empty() && prec.containsKey(operand.peek()) && precedenceOrder(prec, operand.peek(),ch)){
        			rpn.add(operand.pop());
        		}
        		operand.push(ch);
        	}

        }
        while(!operand.isEmpty())
        	rpn.add(operand.pop());
        for(String ch:rpn){
        	System.out.print(ch+",");
        }
        System.out.println();
        return;
    }

    public static void testshuntingYard(){
        String s="1+(20.7*3)-7/(7-5)";
        shuntingYardRPN(s);
    }
    
    public static String getMaximumValue(String input){
    	List<String> inp=stringTokenizer(input);
    	 Map<String,Integer> prec=precedenceOrder();
        assert(inp.size()%2==0);
        int i=0;
        for(String ch:inp){
        	if(i%2==0){
        	 try{
        		 Double.parseDouble(ch);
        	 }
        	 catch(Exception e){
        		 e.printStackTrace();
        	 }
        	}
        	else
        		assert(prec.containsKey(ch));
        	i++;
        }
        
        return  getMaximumValue(inp,0,inp.size()-1).max;
    }

    private static Pair getMaxMinValues(Pair left, Pair right, String op){
    	
    	Double minn;
    	Double maxx;
    	if("/".equals(op) || "-".equals(op)){
    		minn=getOperationValue(Double.parseDouble(left.min),Double.parseDouble(right.max),op);
    		maxx=getOperationValue(Double.parseDouble(left.max),Double.parseDouble(right.min),op);
    	}
    	else{
    		minn=getOperationValue(Double.parseDouble(left.min),Double.parseDouble(right.min),op);
    		maxx=getOperationValue(Double.parseDouble(left.max),Double.parseDouble(right.max),op);
    	}
    	return new Pair(minn.toString(),maxx.toString());
    }
	private static Pair getMaximumValue(List<String> inp, int i, int j) {
		if(i==j)
			return new Pair(inp.get(i),inp.get(j));
		if(j-i==2){
			Double first=Double.parseDouble(inp.get(i));
			Double second=Double.parseDouble(inp.get(j));
			Double val=getOperationValue(first,second,inp.get(i+1));
			return new Pair(val.toString(),val.toString());
		}
		Double minval=Double.MAX_VALUE;
		Double maxval=Double.MIN_VALUE;
		for(int k=i;k<j;k=k+2){
			Pair left=getMaximumValue(inp,i,k);
			Pair right=getMaximumValue(inp,k+2,j);
			Pair cur=getMaxMinValues(left, right, inp.get(k+1));
			
			if(minval>Double.parseDouble(cur.min))
				minval=Double.parseDouble(cur.min);
			if(maxval<Double.parseDouble(cur.max))
				maxval=Double.parseDouble(cur.max);
		}
		return new Pair(minval.toString(),maxval.toString());
	}
	
	public static void testgetMaximumValue(){
		String inp="1+3*7-8/2";
		System.out.println(getMaximumValue(inp));
	}
}
